package com.zlk.algorithm.algorithm.unionAndFind;

/**
 * @program: algorithm
 * @ClassName FriendCircles
 * @description:本题为leetcode原题
 * 测试链接：https://leetcode.com/problems/friend-circles/
 * @author: slfang
 * @create: 2024-03-07 15:05
 * @Version 1.0
 **/
public class Code02_FriendCircles {


    public int findCircleNum(int[][] isConnected) {
        UnionAndFindArray unionAndFindArray = new UnionAndFindArray(isConnected.length);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = i+1; j < isConnected[i].length; j++) {//为啥i+1 因为 isConnected[i][j]==isConnected[j][i]
                if(isConnected[i][j]==1){//相互认识
                    unionAndFindArray.union(i,j);
                }
            }
        }
        return unionAndFindArray.sets();
    }


    class UnionAndFindArray {
        public int[] father ;

        public int[] size ;

        public int[] help ;

        int sets;

        public UnionAndFindArray(int N) {
            father = new int[N];
            size = new int[N];
            help = new int[N];
            sets= N;
            for (int i = 0; i < N; i++) {
                father[i] = i;
                size[i] = 1;
            }
        }


        public void union(int a, int b) {
            int fatherA = findFather(a);
            int fatherB = findFather(b);
            if (fatherA != fatherB) {
                int sizeA = size[fatherA];
                int sizeB = size[fatherB];
                if (sizeA >= sizeB) {
                    father[fatherB] = fatherA;
                    size[fatherA] += sizeB;
                } else {
                    father[fatherA] = fatherB;
                    size[fatherB] += sizeA;
                }
                sets--;
            }
        }

        private int findFather(int cur) {
            int i = 0;
            while (cur != father[cur]) {
                help[i++] = cur;
                cur = father[cur];
            }
            i--;
            while (i >= 0) {
                father[help[i--]] = cur;
            }
            return cur;
        }

        public int sets() {
            return sets;
        }

        // 查询x和y是不是一个集合
        public boolean isSameSet(int x, int y) {

            return findFather(x) == findFather(y);
        }
    }
}
